// https://www.lintcode.com/problem/interleaving-string/my-submissions


// https://leetcode.cn/problems/interleaving-string/submissions/
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int m = s1.length();
        int n = s2.length();
        if (m + n != s3.length()) return false;
        vector<vector<int>> rec(m + 1, vector<int>(n + 1));
        rec[0][0] = true;
        for (int i = 1; i <= m; ++i) {
            // rec[i][0] = (s1[i - 1] == s3[i - 1]);
            rec[i][0] = rec[i - 1][0] && (s1[i - 1] == s3[i - 1]);
        }
        for (int j = 1; j <= n; ++j) {
            rec[0][j] = rec[0][j - 1] && (s2[j - 1] == s3[j - 1]);
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (s1[i - 1] == s3[i + j - 1]) rec[i][j] = rec[i][j] || rec[i - 1][j];
                if (s2[j - 1] == s3[i + j - 1]) rec[i][j] = rec[i][j] || rec[i][j - 1];
            }
        } 
        return rec[m][n];
    }
};



class Solution {
public:
    /**
     * @param s1: A string
     * @param s2: A string
     * @param s3: A string
     * @return: Determine whether s3 is formed by interleaving of s1 and s2
     */
     
    // bool isInterleave(string &s1, string &s2, string &s3) {
    //     int m = s1.length();
    //     int n = s2.length();
    //     int len = s3.length();
    //     if (m + n != len)
    //         return false;
    //     vector<vector<bool>> rec(m + 1, vector<bool>(n + 1, false));
    //     rec[0][0] = true;
    //     // for (int i = 1; i < m + 1; ++i)
    //     // {
    //     //     rec[0][i] = rec[0][i - 1] && (s2[i - 1] == s3[i - 1]);
    //     //     rec[i][0] = rec[i - 1][0] && (s1[i - 1] == s3[i - 1]);
    //     // } 不能一起写，m和n不一定相等！
        
    //     // 写法一：
    //     // for (int i = 1; i < m + 1; ++i)
    //     // {
    //     //     rec[i][0] = rec[i - 1][0] && (s1[i - 1] == s3[i - 1]);
    //     // }
    //     // for (int i = 1; i < n + 1; ++i)
    //     // {
    //     //     rec[0][i] = rec[0][i - 1] && (s2[i - 1] == s3[i - 1]);
    //     // }
    //     // for (int i = 1; i < m + 1; ++i)
    //     // {
    //     //     for (int j = 1; j < n + 1; ++j)
    //     //     {
    //     //         if (s3[i + j - 1] == s1[i - 1])
    //     //             rec[i][j] = rec[i - 1][j];
    //     //         // else if (s3[i + j - 1] == s2[j - 1]) 注意！只要有一种是true就行。
    //     //         if (s3[i + j - 1] == s2[j - 1])
    //     //             rec[i][j] = rec[i][j] || rec[i][j - 1];
    //     //     }
    //     // }
        
    //     // 写法二：
    //     for (int i = 0; i < m + 1; ++i)
    //     {
    //         for (int j = 0; j < n + 1; ++j)
    //         {
    //             if (i == 0 && j == 0)
    //             {
    //                 rec[i][j] = true;
    //                 continue;
    //             }
    //             if (i > 0 && s3[i + j - 1] == s1[i - 1] && rec[i - 1][j])
    //             {
    //                 rec[i][j] = true;
    //             }
    //             if (j > 0 && s3[i + j - 1] == s2[j - 1] && rec[i][j - 1])
    //             {
    //                 rec[i][j] = true;
    //             }
    //         }
    //     }
    //     return rec[m][n];
    // }
    
    
      bool isInterleave(string &s1, string &s2, string &s3) {
        int m = s1.length();
        int n = s2.length();
        int len = s3.length();
        if (m + n != len)
            return false;
        vector<vector<bool>> rec(2, vector<bool>(n + 1));
        int now = 0;
        int old = 0;
        for (int i = 0; i < m + 1; ++i)
        {
            old = now;
            now = 1 - now;
            for (int j = 0; j < n + 1; ++j)
            {
                if (i == 0 && j == 0)
                {
                    rec[now][j] = true;
                    continue;
                }
                rec[now][j] = false; //滚动数组写法直接一开始全初始化为false会出错
                if (i > 0 && s3[i + j - 1] == s1[i- 1] && rec[old][j])
                {
                    rec[now][j] = true;
                }
                if (j > 0 && s3[i + j - 1] == s2[j - 1] && rec[now][j - 1])
                {
                    rec[now][j] = true;
                }
            }
        }
        return rec[now][n];
    }
};